package com.backpack;

import java.util.Arrays;

/**
 * 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
 * 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
 * 输出：3
 * 解释：长度最长的公共子数组是 [3,2,1] 。
 */
public class MaximumLengthofRepeatedSubarray0117_718 {
//    public int findLength(int[] nums1, int[] nums2) {
//        //动态规划思路
//        //dp 含义：以下标 i-1为尾元素的 nums1，和以 j-1为尾元素的 nums2 的两个子数组 重复子数组长度。
//        int[][] dp = new int[nums1.length+1][nums2.length+1];
//
//        //返回值 dp 的最大值
//        int res = 0;
//        //初始化：全为 0；
//
//        for (int i = 1; i <= nums1.length; i++) {
//            for (int j = 1; j <= nums2.length; j++) {
//                if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
//                res = Math.max(dp[i][j],res);
//            }
//        }
//        return res;
//    }


    //法二：压缩数组/滚动数组
    public int findLength(int[] nums1, int[] nums2) {
        //动态规划思路
        //dp 含义：
        int[] dp = new int[nums2.length+1];

        //返回值 dp 的最大值
        int res = 0;
        //初始化：0

        for (int i = 1; i <= nums1.length; i++) {
            for (int j = nums2.length; j > 0; j--) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                }else{
                    dp[j] = 0;
                }
                res = Math.max(dp[j],res);
            }
        }
        return res;
    }
}
